﻿using PrototypeModel;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PrototypeUnitTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //Prototype prototype1 = new ConcretePrototype1("1");
            //Prototype p1 = prototype1.Clone();
            //Prototype prototype2 = new ConcretePrototype2("2");
            //Prototype p2 = prototype2.Clone();
            //Console.WriteLine("p1:{0},p2:{1}", p1.Id, p2.Id);
            FeiBoNaQiShuLie fbnqsl = new FeiBoNaQiShuLie(47995855);
            Console.WriteLine(fbnqsl.Value(20000));
            //Console.WriteLine(Calc(30));
            Console.Read();
        }
        public static long Calc(long n)
        {
            if (n < 1) { throw new IndexOutOfRangeException("n为正整数"); }
            if (n == 1 || n == 2) return 1;
            long result = Calc(n - 1) + Calc(n - 2);
            Console.WriteLine(result);
            return result;
        }
    }


    public class FeiBoNaQiShuLie
    {
        public IDictionary<long, long> dicShuLie { get; set; }
        long max = 0;
        public FeiBoNaQiShuLie(long n)
        {
            if (n < 1) { throw new IndexOutOfRangeException("n为正整数"); }
            dicShuLie = new Dictionary<long, long>();
            max = n;
            for (long i = 1; i <= n; i++)
            {
                Calc(i);
            }
        }
        private long Calc(long n)
        {
            if (n > 2)
            {
                return CacheCalcValue(n - 1) + CacheCalcValue(n - 2);
            }
            return 1;
        }
        private long CacheCalcValue(long n)
        {
            long last;
            if (dicShuLie.ContainsKey(n))
            {
                last = dicShuLie[n];
            }
            else
            {
                last = Calc(n);
                dicShuLie[n] = last;
            }
            return last;
        }
        public long Value(long n)
        {
            if (n > max) { throw new IndexOutOfRangeException("n 不能超过" + max); }
            return dicShuLie[n];
        }
    }
}
